#include <iostream>
#include <string>
#include <list>
#include <unordered_map>
#include <vector>
#include <mutex>
#include <thread>
#include <memory>

using std::pair;
using std::string;
using std::unordered_map;   
using std::vector;
using std::list;
using std::mutex;
using std::shared_ptr;

using std::cout;
using std::endl;

struct CacheNode {
    string key;
    vector<string> value;
};

class LRUCache {
public:
    LRUCache(int capacity)
    : _capacity{ capacity }
    {
        _cache = std::make_shared<list<CacheNode>>();
        _index = std::make_shared<unordered_map<string, list<CacheNode>::iterator>>();
    }

    // 获取缓存中的值
    vector<string> get(string key)
    {
        std::lock_guard<std::mutex> lock(_mutex);
        auto iter = _index->find(key);
        if (iter == _index->end()) {
            // 不存在，直接返回-1
            return {};
        }
        auto entry_iter = iter->second;
        auto value = entry_iter->value;
        _cache->splice(_cache->begin(), *_cache, entry_iter);
        return value;
    }

    // 插入缓存
    void put(string key, vector<string> value)
    {
        std::lock_guard<std::mutex> lock(_mutex);
        auto iter = _index->find(key);
        if (iter != _index->end()) {
            // 存在，更新值
            auto entry_iter = iter->second;
            entry_iter->value = value;
            _cache->splice(_cache->begin(), *_cache, entry_iter);
            return ;
        }

        // 不存在
        _cache->emplace_front(CacheNode{key, value});
        // 构建节点的索引
        _index->insert({key, _cache->begin()});
        if (_cache->size() > _capacity) {
            // 淘汰最后一个元素
            _index->erase(_cache->back().key);
            _cache->pop_back();
        }
    }

private:
    mutex _mutex;
    int _capacity;
    shared_ptr<list<CacheNode>> _cache;
    shared_ptr<unordered_map<string, list<CacheNode>::iterator>> _index;
};

